#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;
class Solution
{
public:
    bool sequenceReconstruction(vector<int> &nums, vector<vector<int>> &sequences)
    {
        // num-index
        // 1-排除特殊情况
        int n = nums.size(), seqSize = sequences.size();

        unordered_map<int, int> numsMap;
        for (size_t i = 0; i < nums.size(); i++)
        {
            numsMap[nums[i]] = i;
        }

        sort(sequences.begin(), sequences.end());
        for (size_t i = 0; i < seqSize; i++)
        {
            for (size_t j = 0; j < sequences[i].size() - 1; j++)
            {
                // 排序且有交集
                if (numsMap[sequences[i][j]] > numsMap[sequences[i][j + 1]])
                {
                    return false;
                }
            }
        }

        return true;
    }

    bool sequenceReconstruction_2(vector<int> &nums, vector<vector<int>> &sequences)
    {
        int n = nums.size();
        vector<int> indegrees(n + 1);
        vector<unordered_set<int>> graph(n + 1);
        for (auto &sequence : sequences)
        {
            for (int i = 1; i < sequence.size(); i++)
            {
                int prev = sequence[i - 1], next = sequence[i];
                // 有向无环图
                if (!graph[prev].count(next))
                {
                    graph[prev].emplace(next);
                    indegrees[next]++;
                }
            }
        }
        queue<int> qu;
        for (int i = 1; i <= n; i++)
        {
            if (indegrees[i] == 0)
            {
                qu.emplace(i);
            }
        }
        while (!qu.empty())
        {
            if (qu.size() > 1)
            {
                return false;
            }
            int num = qu.front();
            qu.pop();
            for (int next : graph[num])
            {
                indegrees[next]--;
                if (indegrees[next] == 0)
                {
                    qu.emplace(next);
                }
            }
        }
        return true;
    }

    bool sequenceReconstruction_3(vector<int> &nums, vector<vector<int>> &sequences)
    {
        int n = nums.size();
        if (n == 0)
            return true;
        if (sequences.empty())
            return false;

        vector<int> mp(n + 1, 0), book(n, 0);
        for (int i = 0; i < n; ++i)
            mp[nums[i]] = i;
        for (auto vec : sequences)
        {
            if (vec[0] > n || vec[0] < 1)
                return false;
            for (int i = 1; i < vec.size(); ++i)
            {
                int a = vec[i - 1], b = vec[i];
                if (b > n || b < 1)
                    return false;
                if (mp[a] >= mp[b])
                    return false;
                if (mp[a] == mp[b] + 1)
                {
                    book[mp[a]] = 1;
                }
                else if (mp[a] == mp[b] - 1)
                {
                    book[mp[b]] = 1;
                }
            }
        }
        for (int i = 1; i < n; ++i)
        {
            if (book[i])
                continue;
            return false;
        }
        return true;
    }
};
int main()
{
    Solution s;
    vector<int> nums = {4, 1, 5, 2, 6, 3};
    vector<vector<int>> sequences = {{5, 2, 6, 3}, {4, 1, 5, 2}};
    cout << s.sequenceReconstruction(nums, sequences) << endl;
    system("pause");
    return 0;
}
